#pragma once
#include <iostream>
#include <algorithm>
using std::cout;
using std::endl;

namespace xyl
{
    template <class K, class V>
    struct BSTNode
    {
        BSTNode(const K &key = K(), const V &value = V())
            : _left(nullptr),
              _right(nullptr),
              _key(key),
              _value(value)
        {
        }

        BSTNode<K, V> *_left;
        BSTNode<K, V> *_right;
        K _key;
        V _value;
    };

    template <typename K, typename V>
    class BSTree // 左小右大
    {
        typedef BSTNode<K, V> Node;
        typedef Node *pNode;
        typedef BSTree<K, V> self;

    private:
        void _prevPrint(pNode root)
        {
            if (root == nullptr)
                return;
            cout << root->_key << " : " << root->_value << " ";
            _prevPrint(root->_left);
            _prevPrint(root->_right);
        }

        /*delete树*/
        void _destroy(pNode root)
        {
            if (nullptr == root)
                return;
            _destroy(root->_left);
            _destroy(root->_right);
            delete root;
        }

        /*拷贝root树，返回新树的root*/
        pNode _copy(pNode root)
        {
            // 递归
            // 递时new 结点
            // 归时连接结点
            if (root == nullptr)
                return nullptr;
            pNode newRoot = new Node(root->_key, root->_value);
            newRoot->_left = _copy(root->_left);
            newRoot->_right = _copy(root->_right);
            return newRoot;
        }

        pNode _find_r(pNode root, const K &key)
        {
            if (nullptr == root)
                return nullptr;
            if (key > root->_key)
                return _find_r(root->_right, key);
            if (key < root->_key)
                return _find_r(root->_left, key);
            return root;
        }

        bool _insert_r(pNode &root, const K &key, const V &value)
        {
            if (nullptr == root) // 可以插入了
            {
                root = new Node(key, value);
                return true;
            }
            if (key > root->_key)
                return _insert_r(root->_right, key, value);
            if (key < root->_key)
                return _insert_r(root->_left, key, value);
            // if (key == root->_key)
            return false;
        }

        bool _erase_r(pNode &root, const K &key)
        {
            if (nullptr == root)
                return false;
            if (key > root->_key)
                return _erase_r(root->_right, key);
            else if (key < root->_key)
                return _erase_r(root->_left, key);

            // 删除
            pNode del = root;
            if (nullptr == root->_left)
                root = root->_right;
            else if (nullptr == root->_right)
                root = root->_left;
            else
            {
                // 找左子树的最大节点
                pNode leftMax = root->_left;
                while (leftMax->_right)
                    leftMax = leftMax->_right;
                root->_key = leftMax->_key;
                return _erase_r(root->_left, leftMax->_key);
            }
            delete del;
            // cout << "delete success.\n";
            return true;
        }

    public:
        BSTree()
            : _root(nullptr)
        {
        }

        ~BSTree()
        {
            _destroy(_root);
            _root = nullptr;
        }

        BSTree(const self &x)
        {
            _root = _copy(x._root);
        }

        self &operator=(self x)
        {
            std::swap(_root, x._root);
            return *this;
        }

        /*前序遍历*/
        void prevPrint()
        {
            _prevPrint(_root);
            cout << endl;
        }

        /*递归查找*/
        pNode find_r(const K &key)
        {
            return _find_r(_root, key);
        }

        /*递归插入数据*/
        bool insert_r(const K &key, const V &value)
        {
            return _insert_r(_root, key, value);
        }

        /*递归删除数据*/
        bool erase_r(const K &key)
        {
            return _erase_r(_root, key);
        }

    private:
        pNode _root;
    };
}